package com.gitee.feizns.explore.data_structure.graph;

/**
 * @author feizns
 * @since 2020/4/29
 */
public class IsBipartite {

    public static void main(String[] args) {
        System.out.println(isBipartite(new int[][]{{1, 3}, {0, 2}, {1, 3}, {0, 2}}));
    }

    private static int[] g;

    private static int[][] G;

    public static boolean isBipartite(int[][] graph) {
        G = graph;
        g = new int[graph.length];
        for (int i = 0; i < graph.length; i++) {
            if ( g[i] == 0 ) {
                g[i] = 1;
                if ( !dfs(i) )
                    return false;
            }
        }
        return true;
    }

    private static boolean dfs(int s) {
        int color = g[s];
        int[] adj = G[s];
        for (int i : adj) {
            if ( g[i] == color )
                return false;
            else if ( g[i] == 0 ) {
                g[i] = color == 1 ? -1 : 1;
                if ( !dfs(i) )
                    return false;
            }
        }
        return true;
    }

}
